
%%%%%%%%%%%%%%%%%%%%%%% file typeinst.tex %%%%%%%%%%%%%%%%%%%%%%%%%
%
% This is the LaTeX source for the instructions to authors using
% the LaTeX document class 'llncs.cls' for contributions to
% the Lecture Notes in Computer Sciences series.
% http://www.springer.com/lncs       Springer Heidelberg 2006/05/04
%
% It may be used as a template for your own input - copy it
% to a new file with a new name and use it as the basis
% for your article.
%
% NB: the document class 'llncs' has its own and detailed documentation, see
% ftp://ftp.springer.de/data/pubftp/pub/tex/latex/llncs/latex2e/llncsdoc.pdf
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentclass[a4paper]{llncs}
\usepackage{ctex}
\usepackage{amssymb}
\usepackage{amsmath}
\setcounter{tocdepth}{3}
\usepackage{graphicx}
\usepackage{array}
\usepackage{multirow}

\usepackage{url}
\urldef{\mailsa}\path|xxx@iie.ac.cn|
%\urldef{\mailsa}\path|{alfred.hofmann, ursula.barth, ingrid.haas, frank.holzwarth,|
%\urldef{\mailsb}\path|anna.kra\usepackage[options]{package}mer, leonie.kunz, christine.reiss, nicole.sator,|
%\urldef{\mailsc}\path|erika.siebert-cole, peter.strasser, lncs}@springer.com|
\newcommand{\keywords}[1]{\par\addvspace\baselineskip
\noindent\keywordname\enspace\ignorespaces#1}
\renewcommand{\abstractname}{摘要}
\renewcommand\refname{参考文献}
\renewcommand\tablename{表}


\usepackage{graphicx}
\graphicspath{{figures/}}
\usepackage[noend]{algpseudocode}

\usepackage{algorithm}
\usepackage{algorithmicx}

\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}
\begin{document}


\mainmatter  % start of an individual contribution

% first the title is needed
\title{RSA快速实现调研报告}

%% a short form should be given in case it is too long for the running head
%\titlerunning{Lecture Notes in Computer Science: Authors' Instructions}

% the name(s) of the author(s) follow(s) next
%
% NB: Chinese authors should write their first names(s) in front of
% their surnames. This ensures that the names appear correctly in
% the running heads and the author index.
%
\author{2020302181062 崔浩然 \inst{1}}%
%\institute{$^1$Institute of Information Engineering, \\Chinese Academy of Sciences, Beijing, China\\
%$^2$School of Cyber Security, \\University of Chinese Academy of Sciences, Beijing, China\\
%\mailsa}
\institute{$^1$武汉大学国家网络安全学院, 武汉，湖北\\}
%\thanks{Please note that the LNCS Editorial assumes that all authors have used
%the western naming convention, with given names preceding surnames. This determines
%the structure of the names in the running heads and the author index.}%
%\and Ursula Barth\and Ingrid Haas\and Frank Holzwarth\and\\
%Anna Kramer\and Leonie Kunz\and Christine Rei\ss\and\\
%Nicole Sator\and Erika Siebert-Cole\and Peter Stra\ss er}
%
%\authorrunning{崔浩然}
% (feature abused for this document to repeat the title also on left hand pages)

% the affiliations are given next; don't give your e-mail address
% unless you accept that it will be published
%\institute{Springer-Verlag, Computer Science Editorial,\\
%Tiergartenstr. 17, 69121 Heidelberg, Germany\\
%\mailsa\\}
%\mailsb\\
%\mailsc\\
%\url{http://www.springer.com/lncs}}

%
% NB: a more complex sample for affiliations and the mapping to the
% corresponding authors can be found in the file "llncs.dem"
% (search for the string "\mainmatter" where a contribution starts).
% "llncs.dem" accompanies the document class "llncs.cls".
%
%\titlerunning{}
% \toctitle{xxx}
% \tocauthor{xxx)}
\maketitle

%
\begin{abstract}
RSA算法是一种公开密钥算法，其加密密钥和算法本身都是公开的，解密密钥则归用户私人所有。从RSA的出现的那天起就因为安全强度高、使用方便而受到关注，并得到广泛的应用。但是，近年来由于分解大整数的能力日益增强，为保证RSA算法的安全性，我们就不得不产生更大的大素数。但该算法所采用的幂模计算会耗费太多的时间，一直是制约其广泛应用的瓶颈。因此，对大整数模幂和模乘算法以及取模算法的加速实现进行研究具有重要的理论意义和实用价值。当前针对RSA的研究主要包括密钥生成的优化、素性检测的优化、大整数模乘和模幂运算的优化等，本文重点研究大数模乘和模幂运算的优化问题。本调研中，对目前流行的蒙哥马利算法进行了研究，并研究了基于滑动窗口编码而提出的新颖的限长游程编码，并将其应用于设计大整数的模乘和模幂运算实现算法。

\keywords{RSA,Montgomery 滑动窗口编码算法, 限长游程编码算法}
\end{abstract}


\section{研究现状}
\indent RSA公钥密码算法是当前最著名、应用最广泛的公钥密码算法，它是由Rivet、shamir、Adelman于1978年提出的。RSA是一种分组加密算法，原理简单，易于使用，先后被ITU、SWIFT等国际化标准组织采用作为标准。
\\ \indent RSA的安全性是依赖于大整数的因子分解的困难性，为了满足信息安全强度的需求，密钥的位数都比较多(512位甚至更高)，导致幂模运算的运算量极大，成为提高RSA算法加解密速度的瓶颈。目前RSA算法主要存在的问题:
(1)产生密钥非常麻烦，受制于当前素数产生技术的限制，因而难以做到一次一密。
(2)安全性，RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，而且密码学界多数人士倾向于因子分解不是NPC问题 。目前，人们己能分解140多个十进制位的大素数，这就要求使用更长的密钥。
(3)速度太慢，由于RSA的分组长度太大，为保证安全性，n至少也要512位以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级; 且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。
\\ \indent 为了做到一次一密，人们一直在寻找快速生成大素数的方法;为了提高RSA算法的加解密速度，人们也一直在寻找、研究各种快速的幂模算法。RSA算法应用非常广泛，而且目前国际上流行的其他几种公钥密码体制也需要大素数和幂模运算，因此，研究RSA算法具有十分重要的意义。
\\ \indent 为了解决大素数运算问题可以采用两种方法，一是改进RSA密码算法的实现，从其算法本身入手，加快其运算速度，本课题就是从这方面的研究入手，来解决其运算速度缓慢的问题。另一个是利用其他的公钥密码算法来替换现在复杂的公钥密码算法，比如采用基于椭圆曲线的公钥密码体制ECC，它的密钥短，256比特的ECC密钥就可以达到对称密钥128比特的安全水平，实现了密钥效率的重大突破，大有以强大的短密钥优势取代 RSA 密码算法成为新一代公钥标准之势 \cite{严洪2005数据加密技术及其发展趋势}。
\\ \indent 但由于RSA公钥密码算法己被广泛地应用在电子商务、电子邮件安全等很多领域，而且其原理简单，使用方便，目前仍为使用最为广泛的一种公钥密码体制。关于RSA密码算法的快速实现的研究是当前一个重要的研究领域，国内外的诸多学者正致力于此，并取得了许多成绩，使RSA密码算法长盛不衰。
\\ \indent 国外一些著名的信息安全公司，如RSA信息安全公司己在某一些产品中应用2048比特以上模长的RSA密码算法，我国学者也提出了一些公钥密码体制的改进办法，另外在公钥密码的快速实现方面也做了一定的工作，比如在RSA的快速实现和椭圆曲线公钥密码的快速实现方面都有所突破。公钥密码的快速实现是当前公钥密码研究中的一个热点，包括算法的优化和程序的优化。
\\ \indent 目前，国内外研究RSA密码算法主要集中在其模幂模乘的快速算法上，主要的快速模幂算法有二进算法、M进算法、因子算法、幂树算法、加法链方法等，快速模乘算法有Karatsuba-ofinan算法、基于FFT的快速模乘算法、以及蒙哥马利算法\cite{schneier2000应用密码学}\cite{koc1994high}。近几年来，国内外诸多学者多数采用了适合于硬件开发的蒙哥马利算法，在实际应用中不断摸索着改进算法的实现方法。另外，国外一些学者提出了将模数分解为几个大素数的乘积，这样就可以利用中国剩余定理更加快速的计算模幂运算\cite{krishnamurthy2003efficient}\cite{vanstone1994using}\cite{胡建军2003中国剩余定理提高}。近年来，有研究人员又提出了以空间换时间的优化思想，从而产生了无符号的滑动窗口编码USW技术和有符号的滑动窗口编码SSW技术\cite{伍红茹2005最佳滑动窗口编码法及其在快速模幂乘中的应用}\cite{hayami2002sliding}。


\section{Montgomery算法}
\indent Montgomery算法是1985年提出的一种有效的模乘算法，其设计思想是借助一个新的特殊剩余系，将普通的模乘转换为易计算的特殊模乘，从而可以用简单的位运算来代替复杂的模运算。此后，人们提出了不少Montgomery的改进算法，1996年Koc总结了该算法的五种实现方法: SOS、CIOS、FIOS、FIPS 和 CIHS,并指出CIOS方法综合性能较优\cite{phillips2000signed}。
\subsection{Montgomery模乘算法}
\indent 模乘是为了计算$ab\ modN$。普通算法中，在计算模N时，利用的是带余除法，除法运算需要太多次乘法，计算复杂度较高，蒙哥马利算法的思想就是利用进制表示简化除法运算，转化成位运算。
\\ \indent Montgomery形式：为了计算$ab\ modN$，找一个R，然后使得$a'\equiv aR \ modN$, $b'\equiv bR\ modN $，这就是Montgomery形式。这个R不是随便一个数，需要满足两个条件：①$R=2^{k} > N$，其中k是满足条件的最小的正数，这个取法能够保证除以R就相当于右移k位，避免除法运算；②GCD(R,N)=1，这使得能够求出下面的m。
\\ \indent 为了计算一开始的$ab \ modN$，需要用到上面的蒙哥马利形式。令$X=a'b'$,我们可以设计一个函数来计算$XR^{-1}\ modN$，简单计算发现这个函数的计算结果为$X_{1}\equiv XR^{-1}\equiv a'b'R^{-1}\equiv abR\ modN$，这样在调用一遍函数计算$X_{1}R^{-1} \ modN$就得到我们最终需要的结果$ab \ modN $了。我们称这个算法交蒙哥马利约简算法。所以说，蒙哥马利约简的产生是为了蒙哥马利模乘计算服务的。
\\ \indent 根据上述分析可知蒙哥马利算法的核心在于蒙哥马利约简。而且前面提到，蒙哥马利算法的主要思想是把取模运算变得简单.主要思想：蒙哥马利约简是计算$XR^{-1}\ modN$，这相当于$X/R\ modN $，如何才能避免除法？从前面的R的定义中我们知道，$R = 2^{k}$,所以$X/R = X \gg k$ （X右移k位）。但是新的问题出现了，右移k位可能会抹掉X的低位中的一些1，如$7/4=0b111\gg 2=0b1=1$，这个不是精确计算，而是向下取整的除法。当且仅当X是R的整数倍时，$X/R$严格等于$X\gg k$。所以我们实际上是找一个m，使得$X+mN$是R的倍数，这样计算$(X+mN)/R\ modN$就可以了。
\\ \indent 我们按照以下方法寻找m，根据R的定义，$GCD(R,N)=1$，根据扩展的欧几里得算法，有$RR'-NN'=1$并且有$0<N'<R$，$ 0< R' <N< R $。(注意这里是$ -NN' $，所以有$ N'=-N^{-1}\ mod R $)
\begin{align}
	X+mN &\equiv 0 (mod R)\\
	XN'+mNN' &\equiv 0 (mod R)\\
	XN'+m(RR'-1) &\equiv 0 (mod R)\\
	XN' &\equiv m (mod R)
\end{align}
这样就求出了m。
\\
\\约简算法总流程
\\提前工作：已知a，b，N，并计算处Montgomery形式中的a',b',R'以及X。
\\ \indent Montgomery reduction(X,R,N):
\\ \indent 1.计算$ N'=-N^{-1}mod R,计算m = XN'(mod R) $;
\\ \indent 2.计算$ y=(X+mN)/R $;将$ X+mN $右移k位;
\\ \indent 3.若$ y>N $,则$ y=y-N $;
\\ \indent 这时的y满足:$ 0<y<2N $。因为$ X<N^{2},m<R,N<R $,所以$ \frac{X+mN}{R}< \frac{N^{2}+R*N}{R} < \frac{RN+R*N}{R}=2N $
\\ \indent 4.返回y
\\
\\Montgomery模乘流程
\\Montgomery Multiply(a,b,N):
\\ \indent 1.计算$ a' \equiv aR(mod N),b'\equiv bR(mod N),X=a'b' $;
\\ \indent 2.调用蒙哥马利约简算法:1$ X_{1}=Montgomery\ reduction(X,R,N)=X/R=abR(mod N) $;
\\ \indent 3.再调用蒙哥马利约简算法:$ y=Montgomery\ reduction(X^{1},R,N)=X^{1}/R=ab(mod N) $;
\\ \indent 返回y。
\\由上面分析，我们可以得到以下定理。
\\ \indent \textbf{定理2.1 假设n和r是互素的两个整数，$ n'=-n^{-1}modr $,则对于所有的整数t，当$ m=t*n' modr $时，$ (t+m*n)/r $是一个整数，则满足$ (t+m*n)/r \equiv t*r^{-1} mod n $。}
\\ \indent 假设有三个均为k比特位长的二进制大整数a,b,n,其中$ 2^{k-1} \le n <2^{k},r=2^{k} $,并且n和r互素，$ n'=-n^{-1}mod r $,则计算$ c=a*b modn $时，可先将a和b转换到新的特殊剩余系(称为n-剩余系)中，假设a和b对应n-剩余系中的数为$\overline{a}$ ,$\overline{b}$,其中$ \overline{a}=a*r mod n, \overline{b}=b*r mod n $。再计算$ t=\overline{a}*\overline{b} , m=t*n' mod r $；然后根据定理2.1，计算得$ \overline{c}=\overline{a}*\overline{b}*r^{-1} mod n $。此时$ 0 \le \overline{c} < 2n $,增加一条减法使$ 0 \le \overline{c} < n $，即可将结果限制在n比特位内，不需要再作复杂的取模运算。Montgomery大整数模乘算法可描述如下：
\begin{algorithm}
	\begin{algorithmic}[1]
		\Require $\overline{a}$,$\overline{b}$,n,r
		\Ensure $\overline{c}=\overline{a*b}$
		\\$ n'=-n^{-1}mod r $;
		\\$ t=\overline{a}*\overline{b} $;
		\\$ m=t*n'\ modr $;
		\\$ \overline{c}=(t+m*n)/r $;
		\If{$ \overline{c} \ge n $}
			\State $ \overline{c}=\overline{c}-n $;//利用简单的减法运算来避免复杂的取模运算。
		\EndIf
		\Return $\overline{c}$;
	\end{algorithmic}
\end{algorithm}
\\这样计算出来的$ \overline{c}=\overline{a}*\overline{b}*r^{-1}mod n = a*r*b*r*r^{-1}mod n = a*b*r mod n = c*r mod n $,因此，只要再做一次计算$ c=\overline{c}*r^{-1}mod n $,这样就可以得到我们所需要的计算结果。

\subsection{Montgomery的SOS实现}
\indent 为加快蒙哥马利大整数模乘算法的计算速度，1990年，Dusse修改了模简化计算\cite{dusse1991cryptographic}，将第2.1节中，描述的蒙哥马利算法中的第3,4步结合起来，用w位的$n_{0}$(其中$n_{0}=-n_{0}^{-1} mod W,W=2^{w}$,w为CPU字长)代替n'，自乘次数由原来的$ 3s^{2} $次降为$ 2s^{2}+s $次，额外空间降为2s+2字。koc于1996年归纳并总结了该算法的5种实现方法，详细地讨论SOS(separated operand scanning)方法:
	\begin{algorithmic}[1]
		\Require a,b,n,$ n_{0} $
		\Ensure $t=\overline{a}*\overline{b}$
		\For{$i=0$;$i<s$;$i++$}
			\State C=0;
			\For{$j=0$;$j<s$;$ j++ $}
				\State  (C,S)=t[i+j]+ a[j]*b[i]+C;
				\State t[i+j]=S;
				\State t[i+s]=C;
			\EndFor
		\EndFor
		\For{i=0;i<s;i++}
			\State C=0;
			\State $m=t[i]*n_{0}modW $;
			\For{j=0;j<s;j++}
				\State (C,S)=t[i+j]+m*n[j]+C;
				\State t[i+j]=S;
			\EndFor
		\State ADD(t[i+s],C);
		\EndFor
		\For{j=0;j<s;j++}
			\State u[j]=t[j+s];
		\EndFor
		\If{$ t \ge n $}
			\State t=t-n;
		\EndIf
		\Return t;
	\end{algorithmic}
上述算法中ADD函数完成进位传递，它先将进位C加到给定数组t[i+s]上，然后逐渐向上传递，直到不会出现进位为止

\subsection{Montgomery模平方算法}
\indent 文献\cite{王金荣2007montgomery}提出了适合于通用32位处理器计算大整数平方的OMMS算法，在该算法中，假设大整数$ a= \sum_{i=0}^{s-1}{a_i}{W^{i}} $，则$ t=a^{2} $ 推导式如下:
\\$ t=a^{2}= 2\sum_{j=1}^{s-1}{a_0}{a_j}{W^{0+j}} + 2\sum_{j=2}^{s-1}{a_1}{a_j}{W^{1+j}} + 2\sum_{j=i+1}^{s-1}{a_i}{a_j}{W^{i+j}} + \\2\sum_{j=s-1}^{s-1}{a_{s-2}}{a_j}{W^{s-2j}} + \sum_{j=0}^{s-1}{a_i}^{2} {W^{i+j}} = \sum_{i=0}^{s-2}\sum_{j=i+1}^{s-1}{a_i}{a_j}{W^{i+j}} + \sum_{i=0}^{s-1}{a_i}^{2} {W^{i+j}} $
\\首先我们计算$ \sum_{i=0}^{s-2}\sum_{j=i+1}^{s-1}{a_i}{a_j}{W^{i+j}} $
然后将结果左移1位并与$ \sum_{i=0}^{s-1}{a_i}^{2} {W^{i+j}} $相加，最后计算得到t。算法可描述如下:
	\begin{algorithmic}[1]
		\For{i=0;i<s-1;i++}
			\State C=0;
			\For{j=i+1;j<s;j++}
				\State (C,S)=t[i+j]+a[j]*a[i]+C;
				\State t[i+j]=S;
			\EndFor
			\State t[i+s]=C;
		\EndFor
		\State $ t=t \ll 1 $;
		\State C=0;
		\For{i=0;i<s;i++}
			\State (C,S)=t[i+i]+a[i]*a[i]+C;
			\State ADD(t[i+i+1],C);
			\State t[i+i]=S;
		\EndFor
		\State t[2s-1]=t[2s-1]+C;
	\end{algorithmic}

\subsection{Montgomery模幂算法}
\indent 蒙哥马利算法通过剩余系转换方法计算大整数的模乘运算，极大地提高了大整数模乘运算的计算速度。但因为从普通剩余系转换到 n-剩余系、计算n'和 n-剩余系又转回到普通剩余系需要额外的时间。所以当对某个模数仅计算一次模乘时，使用蒙哥马利模乘算法并不太值得,而对于同一模数的多次模乘计算则比较合适 (例如模幂运算)。
\\ \indent 文献\cite{丁宏2003快速大数模乘算法及其应用}提出了一种改进的基于滑动窗口技术的模幂算法，由于蒙哥马利模乘的结果不是$ a*b mod n $，而是$ a*b *r^{-1}mod n $,为使蒙哥马利模乘算法适合于模幂计算，文献\cite{王金荣2007montgomery}对模幂算法做了适当改进，用w位的$ n_0 $($ n_0=-n_0^{-1}modW.W=2^{w} $，w为CPU字长)代替n'，得到MME(Montgomery Modular Exponentiation)算法如下:
\begin{algorithmic}[1]
	\Require m,e,n,r,$ r_2 $,$ n_0 $
	\Ensure $ c=m^{e}mod n $
	\State $\overline{c}$=r;
	\State $ temp[1]=SOS(m,r_2,n,n_0) $;
	\State $ m_2=OMMS(temp[1],n,n_0) $;
	\For{i=3;$ i<2^{size}-1;i++ $}
		\State $ temp[i]=SOS(temp[i-2],m_2,n,n_0) $;
	\EndFor
	\State e'=Recoding(e);
	\For{$ i=d-1;i \ge 0;i-- $}
		\State $ \overline{c}=OMMS(\overline{c},n,n_0) $;
	    \If{$ e'==1 $}
			\State $\overline{c}$=$ SOS(\overline{c},temp[stack[top--]],n,n_0) $;
		\EndIf
	\EndFor
	\State $ c=SOS(\overline{c},1,n,n_0) $;
	\Return c;
\end{algorithmic}
\indent 其中SIZE表示窗口长度；Recording操作使用滑动窗口技术对指数进行重编码函数，重编码时将当前窗口的值，依次入栈stack，top为指向栈顶的指针，e'为重编码后的指数，d为e'的二进制长度；上述算法中的$ temp[1]=SOS(m,r_2,n,n_0) $将普通剩余系的整数m转化为n-剩余系中的m'，这是因为$ \overline{m}=m*r*r*r^{-1}mod n= m*r mod n $。并将$\overline{m}$存于temp[1]中。随后由$\overline{m}$计算$ \overline{m}^{i}(i=3,5,.....,\overline{m}^{size}-1) $一并存于temp数组中。算法的if语句将n-剩余系中的$\overline{x}$转换成普通的x，这是因为$ \overline{x}*1=\overline{x}*1*r^{-1}mod n=x*r*r^{-1}mod n=x $。


\section{限长游程编码算法}

\subsection{基于滑动窗口的模乘算法}
\indent 有符号的滑动窗口编码技术使用码元集合$ \left\lbrace 1,3,5,...,2^{m}-1 \right\rbrace  $ 将一个二进制数转换成具有较少的非0数字的编码形式。例如，对二进制数$ B=(1011111011101100000111100)_2$,采用滑动窗口编码，取窗口宽度为m=4，从而得到使用的码元集合为$ \left\lbrace 1,3,5,7,9,11,13,15\right\rbrace  $,编码后B的非零元素集合为$ B=\left\lbrace1,15,11,11,15\right\rbrace   $。
\\ \indent 为了方便地在大整数模乘运算中使用该滑动窗口编码方法 ，需要创建三个线性表来存储相应的中间值，设这三个线性表分别为X、T、L。先用滑动窗口技术对其中一个大乘数B的二进制形式重新编码，其中的非0元素保存在线性表X中，如上面例子中，$ X=\left\lbrace 1,15,11,11,15\right\rbrace  $，而线性表T用于存放滑动窗口编码码元与A的模乘的值。线性表L保存线性表X中的元素i与A的积比元素i-1与A的积需要多做的倍乘次数，最后再根据这三个线性表中存储的值来计算 $ A*B mod N $。也就是说，线性表T和L中的元素分别为:$$ T[i]=(2i+1)-AmodN,i=0,1,2,....2^{m-1}-1 $$ $$ L[0]=Z_i,L[i]=Z_i+m,i=2,3,...,len $$

\subsection{基于滑动窗口的模幂算法}
\indent 大整数的模幂运算可以方便的转化为模乘运算，只要将线性表T用于存放($ A,A^{3},A^{5},...A^{2m-3},A^{2m-1} mod N $)的值则可非常容易扩广应用于大整数的模幂运算

\subsection{限长游程编码算法}
\indent 基于滑动窗口编码算法，受到该算法以空间换取时间的算法思想的启发，同样采用以空间换取时间的思想，设计了一种新颖的编码方法---限长游程编码技术
\\ \indent 限长游程编码技术用于对一个n位的二进制数A进行重新编码，如果我们记$ A=(a_{n-1}a_{n-2}...a_{1}a_0)_{2} $，编码时所有的0 bit位都不参与编码，仅作相应的记录，码元集合使用，即仅对二进制数中的1游程进行编码。根据RSA密码体制中大整数模乘和模幂运算的应用需求，我们限定最大码元长为m，即最大码元为$ 2^{m}-1 $。
\\ \indent \textbf{定义3.3.1 游程: 一个游程定义为一个具有相同符号的连续串，在它前后相接的是与其不同的符号或完全无符号。}
例如1游程，指的就是一串1，它的前后都不是1，而本文中的限长1游程实际上是指被截断的1游程，取游程的时候人为限制其长度不得超过定长。
\\ \indent \textbf{定义3.3.2 差位: 对一个二进制数进行编码，对于编码结果集中的元素，第i个元素与第i-1个元素的位移差称为“差位”。}
\\ \indent 限长游程编码的具体编码过程描述如下:
\\  \indent 1)将长为n的待编码的大整数B扩展为n+1位，在B的第n位上置0， 记扩展后的乘数为B'。根据本课题应用的需求，初始化差位计数器count=O，游程计数器lcount=0。对B'从右向左扫描(实际上也可以从左向右扫描，但是从右向左扫描更适合计算机的操作，对后续算法设计也更方便)，对所有的0 bit位都不进行编码。
\\ \indent 2)扫描到最高位，停止扫描; 否则，转到第(3)步。
\\ \indent 3)向左扫描B'，若扫描到1，转到(4) ; 若扫描到0，转到(5) 。
\\ \indent 4)lcount=lcount+ l，检查 Icount的当前值，若 lcount=l，记录当前lcount的值，然后置lcount=l，继续向左扫描;若lcount=m，计算count=count+l，并将该游程编码为$ 2^m-1 $，然后置lcount=0，继续向左扫描;否则，count = count+ 1，继续向左扫描。
\\ \indent 5)count = count + l ，检查 lcount的当前值，若lcount不为0，说明还有1游程未编码，将前面的长为lcount的1游程进行编码 ，置lcount =0，继续扫描; 否则继续扫描。

\subsection{基于限长游程编码的快速模乘算法}
\indent 在做大整数的模乘运算前，我们先利用限长游程编码技术对其中的大乘数B的二进制形式进行重新编码，建立三个线性表来存储相应的中间值，其中码元与A的模乘用线性表T来存储，乘数B编码后的非零元素与A的乘积线性表X来存储，而用线性表L存储线性表X中的差位，然后根据这三个线性表中存储的值来计算$ AB mod N  $的值
\\ \indent 算法3.4 (快速模乘算法)\cite{mcivor2004modified}利用限长游程编码对乘数B进行重新编码，创建三个线性表X,T和L，然后根据这三个线性表中存储的中间值计算AB mod N，假设乘数，正整数A和B的二进制形式位数不比模数N长。
\begin{algorithmic}[1]
	\Require A,B,N,m
	\Ensure C=AB mod N
	\\//1.根据m值计算出码元集合，创建线性表T，其中$ T[i-1]=(2^i-1)AmodN,i=1.2.3...,m $
	\State $ S=2^n mod N $;//n由$ 2^{n-1}<N\le2^{n} $决定
	\State T[0]=A;i=1;P=A;
	\While{i<m}
		\State $ P\ll 1  $;
		\While{carry(P)}
		//carry(P)表示当P的长度大于n时返回1，且进位数清0，否则返回0.
			\State P=P+S;
		\EndWhile 
		\State T[i]=T[i-1]+P;
		\While{carry(T[i])}
			\State T[i]=T[i-1]+S;
		\EndWhile
		\State i++;
	\EndWhile
	//2.利用限长游程编码技术对大乘数B进行重新编码，创建线性表X和L
	\State count=0;
	\State lcount=0;
	\State i=0;k=0;
	\State extend(B);//扩展乘数B为n+1位，在高位置0
	\While{$ i\le n $}
		\If{$ b_i == 1 $}
			\State lcount++;
			\If{lcount==1}
				\State L[k]=count;count=1;
			\Else 
				\State count++;
				\If{lcount==m}
					\State X[k]=T[m-1];k++;lcount=0;
	            \EndIf
	        \EndIf
	    \Else
	     	\State count++;
	     	\If{lcount!=0}
	     		\State X[k]=T[lcount-1];k++;lcount=0;
	     	\EndIf
	    \EndIf
	     \State i++;
	 \EndWhile
	 //3.利用线性表X和L计算$ A*B modN $
	 \State C=0;
	 \State i=k-1;//k为B编码后的非零元素个数
	 \While{ $i\ge 0$ }
	 	\State $ C=(C+X[i])\ll L[i] $;
	 	\While{carry(C)}
	 		\State	C=C+S;
	 	\EndWhile
	 	i--;
	 \EndWhile
	 \If{$ C \ge N $}
	 	\State C=C-N;
	 \EndIf
	 \Return C;
\end{algorithmic}

\subsection{基于限长游程编码的快速模幂算法}
\indent 在做大整数的模幂运算之前，我们首先使用限长游程编码对大指数B的二进制形式进行重新编码，假设编码之后$ B=b_{k}'b_{k-1}'...b_{1}'b_{0}' $。同时建立三个线性表X、T和L来存储相应的中间值，其中线性表T用来存储$ (A,A^{3},...A^{2^{m}-1})mod N $的值，线性表X用来存储$ (A^{b_{k}'},A^{b_{k-1}'},...A^{b_{1}'},A^{b_{0}'})mod N $的值。假设线性表X中的第i个元素需要比第i-1个元素多做 $ x_{i} $ 次平方，我们就称$ x_{i} $为第i个元素和第i-1个元素的“差位”(见定义 5.2)。我们将所有的差位存储在线性表L中。最后，我们利用创建好的三个线性表来计算$ A^{B}modN $的值。
\\ \indent 算法3.5 假设有三个正的大整数A，B和N，我们的目标是计算$ A^{B}modN $。首先，使用限长游程编码做初始化，创建三个线性表T，X和L。然后利用这三个线性表中存储的值来计算$ A^{B}modN $。假设$ B=b_{n-1}...b_{1}b_{0} $。并且A的二进制形式不比N长。详细算法步骤如下:
\begin{algorithmic}[1]
	\Require A,B,N,m
	\Ensure $ C=A^{B}modN $
	\\//1.根据m值创建线性表T，其中$ T[i-1]=A^{2^{i}-1}modN,i=1,2,...,m $
	\State T[0]=A;//初始化第一个元素
	\State i=1;//初始化相关的序号
	\While{i<m}
		\State T[i]=T[i-1]*T[i-1]mod N;
		\State T[i]=T[i]*a modN;
		\State i++;
	\EndWhile
	//2.使用限长游程编码对B进行重新编码，并创建线性表X和L
	\State count=0;//初始化差位数
	\State lcount=0;//初始化游程数
	\State i=0;k=0;
	\State extend(B);//对指数B进行扩展
	\While{$ i\le n $}
		\If{$ b_{i}==1 $}
			\State lcount++;
			\If{lcount==1}
				\State L[k]=count;
				\State count=1;
			\Else
				\State count++;
				\If{lcount==m}
					\State X[k]=T[m-1];
					\State k++;
					\State lcount=0;
				\EndIf
			\EndIf
		\Else
			\State count++;
			\If(lcount!=0)
				\State X[k]=T[lcount-1];
				\State k++;
				\State lcount=0;
			\EndIf
		\EndIf
		\State i++;
	\EndWhile
	//3.利用线性表X和L计算$ C=A^{B}modN $
	\State i=k;j=1;C=1;
	\While{$ i \ge 0 $}
		C=C*X[i]modN;
		\While{j<L[i]}
			\State C=C*Cmod N;j++;
		\EndWhile
		i--;
	\EndWhile
\end{algorithmic}

\section{优缺点}

\indent 限长游程编码技术的提出，是为了改进用于大数模乘运算的滑动窗口技术，减少码元集合，从而节约空间，提高效率。与滑动窗口编码技术相比，限长游程编码的优越性体现在以下几点:
\\ \indent 1. 适应最低位为0，最高位非0的特殊情况。限长游程编码技术不需要对大数
作任何扩展就能适应最低位为0的情况。只需要在最高位上扩展一位并置为0，就能够适应最高位非0的情况，这使得编码算法非常简洁。
\\ \indent 2. 采用的码元集减小。在滑动窗口编码技术中取窗口宽度m，则使用的码元集为{1,3,5,..., $ 2^m-1 $ } ，码元总数为$ 2^m-1 $个; 而本文设计的限长游程编码技术取码元上限长为m时，则码元集为{$ 2^{1}-1,2^{2}-1,...,2^{m}-1 $}，码元总数为m，数量减少了$ 2^m-1 $个。
\\ \indent 3. 完全避免了对0 bit位的计算。在大数模乘运算中，采用重编码技术的旨意就是尽量减少大整数中0元素，避免对0乘一个大整数的操作。在滑动窗口编码中，码元二进制形式中仍然包含0 bit位，而本文提出的限长游程编码技术跳过了所有的0 bit位。


\section{应用场景}
\indent RSA公钥密码体制的快速实现是一个非常复杂而且艰巨的工程。其中包括密钥生成的优化、素性检测的优化、大整数模乘和模幂运算的优化等等。本文抓住了影响RSA快速实现的主要瓶颈，即其主要采用的大整数模乘和模幂运算，研究了古今中外对大整数模乘和模幂运算的优化成果，作出创新算法设计。设计了一种新颖的编码方法--限长游程编码。使得算法能够采用以空间换取时间的思路实现。对编码方法过程进行了详细的描述，并编写代码模拟实现。该编码方法比滑动窗口编码方法简洁易懂，实现操作更简单方便，码元集小，占用空间小，码元与大整数的乘幂运算效率更高。为快速模乘模幂算法的设计提供了高速实现的基础。

\section{未来趋势}
\indent 随着信息时代的发展，安全问题的日益严重，RSA公钥密码体制的应用需求越来越强烈，RSA密码算法的快速实现问题是亚待解决的。本课题的研究，为RSA等公钥密码体制的快速实现提供了一种新的解决思路


\bibliographystyle{./splncs03}
\bibliography{./mybib}

\end{document}
